package com.gitee.feizns.explore.data_structure.recursive;

import java.util.HashMap;
import java.util.Map;

/**
 * 第 K 个语法符号
 * @author feizns
 * @since 2019/12/10
 */
public class KthGrammar {

    public static void main(String[] args) {
        System.out.println(kthGrammar(3, 3));
    }

    private static Map<Integer, String> CACHE = new HashMap<>();

    static {
        CACHE.put(1, "0");
    }

    public static int kthGrammar(int N, int K) {
        return kthGrammar("0", N, K).charAt(K - 1) - '0';
    }

    public static String kthGrammar(String original, int N, int K) {
        StringBuilder ret = new StringBuilder();
        for (int i = 0; i < original.length() && i * 2 <= K; i++) {
            char item = original.charAt(i);
            if ( item == '0' )
                ret.append("01");
            else if ( item == '1' )
                ret.append("10");
        }
        return N != 0 ? kthGrammar(ret.toString(), N - 1, K) : ret.toString();
    }

}
